package o_athletes;

import chapter02.MyUtil;

import java.io.*;
import java.util.Scanner;

public class athletes {

    /**
     * 羽毛球队有男女运动员各n人。给定2个n×n矩阵P和Q。
     * P[i][j]是男运动员i和女运动员j配对组成混合双打的男运动员竞赛优势；
     * Q[i][j]是女运动员i和男运动员j配合的女运动员竞赛优势。
     * 由于技术配合和心理状态等各种因素影响，P[i][j]不一定等于Q[j][i]。
     * 男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为P[i][j]*Q[j][i]。
     * 设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大
     */

    private static int n;//人数
    private static int[][] p,q;//同上
    private static int[] r;//记录当前优势
    private static int best;//最大值

    private static void backtrack(int t){
        //回溯
        if(t>n){
            int temp = 0;
            for(int i=1; i<=n; i++){
                temp += p[i][r[i]] * q[r[i]][i];
            }
            if(temp > best)
                best = temp;
        }else{
            for(int j=t; j<=n; j++){
                MyUtil.swap(r,t,j);
                if(position(j)){
                    backtrack(t+1);
                }
                MyUtil.swap(r,t,j);
            }
        }
    }
    //判断
    public static boolean position(int k){
        for (int i = 0; i < k; i++) {
            if(r[k]==r[i]){
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) throws IOException {
        long startTime=System.currentTimeMillis();
        FileInputStream fileInputStream = null;
        try {
            fileInputStream = new FileInputStream("src\\o_athletes\\test\\pref5.in");
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        Scanner scanner =new Scanner(fileInputStream);
        best = 0;
        n = scanner.nextInt();
        p = new int[n+1][n+1];
        q = new int[n+1][n+1];
        r = new int[n+1];
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                p[i][j] = scanner.nextInt();
            }
        }MyUtil.printM(p,1,3);
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                q[i][j] = scanner.nextInt();
            }
        }
        MyUtil.printM(q,1,3);

        for(int i=1; i<=n; i++)
            r[i] = i;
        backtrack(1);
        System.out.println(best);
        long endTime = System.currentTimeMillis();
        System.out.println("程序的执行时间：" + (endTime - startTime));
        File f=new File("src\\o_athletes\\answer\\prf5.out");
        f.createNewFile();
        FileOutputStream fileOutputStream = new FileOutputStream(f);
        PrintStream printStream = new PrintStream(fileOutputStream);
        System.setOut(printStream);
        System.out.println(best);
        printStream.close();
        fileOutputStream.close();
        fileInputStream.close();
    }
 }
